class Solution {
    // 把结果都缓存一下吧，不然就超时了
    private Map<Integer, Integer> cache = new HashMap<>();
    public int rob(int[] nums) {
        return dp(nums);
    }
    private int dp(int[] nums) {
        int[] temp = new int[nums.length + 1];
        System.arraycopy(nums, 0, temp, 1, nums.length);
        temp[0] = 0;
        nums = temp;
        int[] f = new int[nums.length];
        f[0] = 0;
        f[1] = nums[1];
        for (int i = 1; i < nums.length; i++) {
            if (i >= 2) {
                f[i] = Math.max(f[i], f[i-2] + nums[i]);
            }
            f[i] = Math.max(f[i], f[i-1]);
        }
        return f[nums.length - 1];
    }
    private int findMaxSum(int[] nums, int index) {
        if (cache.containsKey(index)) {
            return cache.get(index);
        }
        if (index >= nums.length) {
            // 最后没人可偷肯定就是0啦
            cache.put(index, 0);
            return 0;
        }
        // 不偷这一家，从下一家开始算，看最多能偷多少
        int sum1 = findMaxSum(nums, index + 1);
        // 偷这一家，从下下家开始算，看最多能偷多少
        int sum2 = nums[index] + findMaxSum(nums, index + 2);
        // 返回最大值就可以了
        int ans = Math.max(sum1, sum2);
        cache.put(index, ans);
        return ans;
    }
}
